public class Sort {

    //插入排序
    public static void insertSort(int[] nums){
        for(int i = 1;i<nums.length;i++){
            for(int j = i-1;j>=0;j--){
                if(nums[j+1]>nums[j]){
                    break;
                }else{
                    int temp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }
    //归并排序
    public static void mergeSort(int[] nums){
        mergeSortTmp(0,nums.length-1,nums);
    }
    public static void mergeSortTmp(int left,int right,int[] nums){
        if(left>=right){
            return;
        }
        int mid = left+(right-left)/2;
        mergeSortTmp(left,mid,nums);
        mergeSortTmp(mid+1,right,nums);
        //合并
        merge(left,right,mid,nums);
    }
    public static void merge(int left,int right,int mid,int[] nums){
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int s2 = mid+1;
        while(s1<=mid && s2<=right){
            if(nums[s1]<=nums[s2]){
                tmp[k++] = nums[s1++];
            }else{
                tmp[k++] = nums[s2++];
            }
        }
        while(s1<=mid){
            tmp[k++] = nums[s1++];
        }
        while(s2<=right){
            tmp[k++] = nums[s2++];
        }
        for(int i = left;i<=right;i++){
            nums[i] = tmp[i-left];
        }
    }
}
